
\section{Introduction}
\vspace{-0.15in}
A well-studied randomized information propagation process in networks
is the (standard) {\em random walk}. In a random walk, in each step,
the current node (the one that has the piece of information) chooses a
random neighbor to pass the information.  Random walk is a fundamental
primitive useful in a wide variety of network applications ranging
from token management and load balancing to search, routing,
information propagation, gathering, and gossip
(e.g.,\cite{DNP09-podc,DNPT10-podc,BBSB04,ZS06} and the references
therein).  Random walks are local and lightweight and require little
index or state maintenance which make them especially attractive to
self-organizing dynamic networks such as Internet overlay and ad hoc
wireless networks \cite{ZS06}. An important parameter of interest in a
random walk is the {\em cover time} --- the (expected) number of
rounds needed till the walk visits all the nodes in the network.
Random walks are communication efficient in the sense that there is
only a single ``active" node holding the information at any step; thus
only constant work (i.e., communication or number of messages
transmitted) is performed per round in a random walk.  However, the
price is the cover time can be quite high in general --- $\Theta(n^3)$
in the worst case (see e.g., \cite{lovasz-survey}). In fact, even in
{\em expander networks}, an important class of graphs which have good
connectivity properties and arise in a number of network applications
(see e.g., \cite{Wigderson-exsurvey}), the cover time is polynomially large
--- $\Theta(n \log n)$ \cite{lovasz-survey}. Hence, several recent
works have addressed the issue of speeding up the cover time of random
walks~\cite{AHKV03,berenbrink,DP05}. In many of these works the main
approach to speed up is by slightly modifying the random walks ---
e.g., visiting additional (constant) number of neighbors of the
current node, while proceeding with the random walk as usual.  The
typical speedup given by these approaches is not very large, the cover
time remains still polynomial. In particular, in expander graphs the
speed up is by a logarithmic factor~\cite{berenbrink}. This raises the
question whether we can speed up random walks significantly (at least
in important classes such as expanders), by modifying the
process. This is one main motivation of the current paper.

In this paper, we study a new distributed randomized information
propagation mechanism in networks that we call a {\em branching random
  walk (BRW)}.  BRW is a generalization of the (standard) random walk,
and is parameterized by a {\em branching factor} $k$.  The process
starts from an arbitrary node, which is labeled {\em active} for step
$1$.  For instance, this could be a node that has a piece of data,
rumor, or a virus. In a BRW, in any step, each active node chooses $k$
random neighbors to become active for the next step.  Note that a node
is active for step $t$ only if it is chosen by an active node in step
$t-1$.  This results in a branching type process in the underlying
network which has interesting properties that are strikingly different
from the standard random walk, which is equivalent to BRW with
branching factor $k=1$. Similar to the standard random walk, we focus
on the {\em cover time}, which is the the number of steps for the walk
to reach all the nodes and the {\em $\delta$-cover time}, which is the
number of steps needed for the walk to reach at least a $\delta$
fraction of the nodes.

We derive almost-tight bounds on cover time and partial cover time in
{\em expander} graphs. Expanders are a very important class of graphs
that have applications in various areas of computer science
---networks, crypography, derandomization, complexity and coding
theory etc. (e.g., see ~\cite{Wigderson-exsurvey} for a survey). For
example, in distributed computing and networks, they have been used
for censorship resistant
networks~\cite{FiatSaiaCensorTOC2007,FiatSaiaCensorSODA02}, fault
tolerant networks~\cite{PippengerLinJournalFaultNets94}, analyzing
information spreading in networks~\cite{HillelPODC10}, and efficient
(Byzantine) agreement and leader election algorithms \cite{DPPU88,
  Upfal94, KSSV06, KS10, APRU2012:Towards}.

 A main contribution of this paper is the analysis of the cover time and partial cover time of BRW 
  in a (bounded-degree) expander. We show that the cover time in a $n$-node expander  is $O(\log n)$ 
(even with branching factor 2,
assuming sufficiently large expansion) and the partial cover time is
$O(\log^2 n)$ with high probability. Since the cover time of standard
random walk is $\Theta(n \log n)$ in an expander, this shows that BRW
gives an exponential speedup. This also implies that the total number of messages sent is $O(n \log n)$  for
partial coverage and $O(n \log^2 n)$ for full coverage. We note that this is essentially optimal and is within
only a logarithmic factor compared to the cover time of the standard random walk (which is BRW with branching
factor 1). Thus, increasing the branching factor to just 2 in every time step, yields an exponential speedup compared
to branching factor 1, 
while not increasing the total message complexity by too much. 
%This can be a thought of a type
%of  {\em two choices} paradigm (\cite{balanced}) applying in the context of random walks in networks. 

We believe that our BRW results can also be generalized to understand
the time taken for an epidemic process in an SIS-type model to spread
in a network~\cite{GANESH,KES,PIET}.  By varying the branching factor
and the time that a node remains infected, the process can also be
viewed as a generalized rumor spreading model, with applications in
both epidemiology and information dissemination.

\iffalse

While the persistence time and
epidemic density of SIS-type epidemic models are well
studied~\cite{GANESH,KES}, here we analyze the time needed for a
SIS-type process to affect a constant fraction of the network.

In this paper, we study a new gossip model that we believe better
models several spreading phenomena.  Our model is best captured by the
following ``branching process'' on a finite graph $G$.  Let $S_t$
denote the set of active nodes in $G$, with $S_0$ being the initial
set of active nodes (usually this is a singleton set).  In round $t$,
each node in $S_{t-1}$ selects $k$ nodes uniformly at random (say,
with replacement) from its set of neighbors; $S_t$ is the union of all
the nodes selected in round $t$.  We focus on two questions: 

how long does it take for the information to reach a constant fraction
of the nodes?

how long does it take for the information to reach all the nodes?

It is instructive to consider the cases of $k = 1$ and $k = 2$.  The
case $k = 1$ is precisely a random walk in the graph, and we need not
discuss it further.  It is not hard to see that the case $k = 2$ will
eventually cover all the nodes; it is interesting to see how it
compares with the standard push process.  The standard push process
takes linear time to complete on the line graph.  The branching
process, however, will take $\Theta(n^2)$ to complete.

\fi


\vspace{-0.15in}
\subsection{Our results} 
\vspace{-0.1in}
We analyze the partial and full cover times of branching random walks
on bounded-degree regular expanders.  We say that a graph is an
$(\alpha,\delta)$-expander if the number of neighbors of every vertex
set $S$ of vertices of size at most $\delta n$ is at least
$\alpha|S|$.  (Note that the neighbors of vertices in $S$ may include
vertices in $S$.)

\begin{itemize} 
\item We show that for any $\Delta$-regular $n$-vertex $(\alpha,
  \delta)$-expander, the $k$-branching random walk covers at least
  $\delta n$ nodes in $O(\log n)$ steps for $k \ge 1 +
  \ln(2\Delta/(\alpha-1))$ assuming $\alpha$ is sufficiently large.
  In particular, for any random regular graph, the 2-branching random
  walk covers $\Omega(n)$ nodes in $O(\log n)$ steps with high
  probability.

\item We show that the cover time of a $k$-branching random walk on
  any bounded-degree regular $(\Omega(n), \alpha)$-expander graph is
  $O(\log^2 n)$ for $k \ge 1 + \ln(2\Delta/(\alpha-1))$, assuming
  $\alpha$ is sufficiently large.  In particular, the cover time of
  the 2-branching random walk on any random regular graph with
  constant degree is $O(\log^2 n)$.
\end{itemize}
\junk{We also extend the analysis of partial coverage to the SIS model.
\begin{itemize}
\item
If the ratio of the infection rate to the cure rate is sufficiently
high and the epidemic persists, then the epidemic reaches a constant
fraction of the nodes in $O(\log n)$ steps, with high probability.
\end{itemize}}

\vspace{-0.15in}
\subsection{Related work}
\vspace{-0.1in}
The study of random walks on graphs has a rich history, and we refer
the reader to~\cite{lovasz-survey,upfal} for a survey.  A classic
result of Aleliunas shows that the cover time of a random walk on an
undirected $n$-vertex $m$-edge graph is at most $2nm$. 
% Bounds in
%terms of spectral properties of graphs and tighter bounds for
%arbitrary graphs were obtained in~\cite{broder-karlin,chandra,feige}.

With the rapidly increasing interest in diffusion processes in
large-scale networks and the gossiping paradigm, there have been a
number of studies on speeding up random walks.  One of the earliest
studies is due to Adler et al~\cite{AHKV03}, who studied a process on
the hypercube in which in each round a vertex is chosen uniformly at
random and covered; if the chosen vertex was already covered, then an
uncovered neighbor of the vertex is chosen uniformly at random and
covered.  For any $d$-regular graph, Dimitrov and Plaxton showed that
a similar process achieves a cover time of $O(n + (n \log
n)/d)$~\cite{DP05}.  For expander graphs, Berenbrink et al\ showed a
simple variant of the standard random walk that achieves a linear
cover time~\cite{berenbrink}.

It is instructive to compare BRW with other mechanisms to speed up
random walks as well as with gossip-based rumor spreading mechanisms.
Perhaps the most related mechanism is that of parallel random walks
which was first studied in~\cite{broder} for the special case where
the starting nodes are drawn from the stationary distribution, and
in~\cite{AAKKLT} for arbitrary starting nodes.  Nearly-tight results
on the speedup of cover time as a function of the number of parallel
walks have been obtained by~\cite{ElsasserS09} for several graph
classes including the cycle, $d$-dimensional meshes, hypercube, and
expanders.  (Also see~\cite{ER09} for results on mixing time.)  Though
BRWs are similar to parallel random walks in the sense that at any
step multiple nodes may be selecting random neighbors, there are
significant differences between the two mechanisms.  First the cover
times of these walks are not comparable.  For instance, while $k$
parallel random walks may have a cover time of $\Omega(n^2/\log k)$
for any $k \in [1,n]$~\cite{ElsasserS09}, a $2$-branching random walk
on a line has a cover time of $O(n)$.  Second, while the number of
active nodes in $k$ parallel random walks is always $k$, the number of
active nodes in any $k$-branching random walk is continually changing
and {\em may not even be monotonic}.  Most importantly, the analysis
of cover time of BRWs needs to address several dependencies in the
process by which the set of active nodes evolve; we use the machinery
of time-inhomogenous Markov chains to obtain the $O(\log^2 n)$ bound
on the cover time for bounded-degree expanders~\cite{MIH} (see
Section~\ref{sec:cover}).

The works of \cite{DNP09-podc,DNPT10-podc} presented  fast distributed algorithms for performing (standard)  random walks. The goal is to improve the round complexity of the standard walk --- which takes $\ell$ rounds
to do a walk of length $\ell$.  The above works  present a sublinear time distributed algorithm for performing random walks whose time complexity is sublinear in the length of the walk.  In particular, the algorithm of \cite{DNPT10-podc}  performs a random walk of length $\ell$  in $\tilde{O}(\sqrt{\ell D})$  rounds with high probability on an undirected  network, where $D$ is the diameter of the network.  The high-level idea behind the algorithm is to perform
several short walks in parallel and then stitch them carefully.   However, this speed up comes with  a drawback: this the message complexity of the above faster algorithm is much worse compared to the naive sequential walk which takes only $\ell$ messages. In contrast, we note that the exponential speedup given by BRW  over the standard 
comes only at the cost of a slightly worse  message complexity.

Gossip-based information propagation mechanisms have also been used for information (rumor) spreading in distributed networks.
%Gossip-based algorithms have also been successfully to {\em design} efficient
%distributed algorithms for a variety of problems in networks such as
%information dissemination, aggregate computation, constructing overlay
%topologies.
%Such local algorithms are considered natural mathematical  models of how spreading
%occurs in real-world networks. 
 In the most typical rumor spreading models, gossip involves either a
 push step, in which nodes that are aware of a piece of information
 (being disseminated) pass it to random neighbors, or a pull step, in
 which nodes that are unaware of the information attempt to extract
 the information from one of their randomly chosen neighbors, or some
 combination of the two.  In such models, the knowledgeable nodes or
 the ignorant nodes participate in the dissemination problem in {\em
   every} round (step) of the algorithm.  \junk{ Rumor spreading and
   related gossip-based processes have been extensively analyzed in
   recent years (see e.g., \cite{panconesi1, panconesi2, panconesi3,
     gia1, gia2, pana1, pana2} and the references therein).} The main
 parameter of interest in many of these analyses is the number of
 rounds needed till all the nodes in the network get to know the
 information.
%It is known that in any graph, rumor spreading takes $O(n \log n)$ rounds.

The rumor spreading mechanism that is most closely related to BRWs is
the basic push protocol, in which in every step every informed node
selects a random neighbor and pushes the information to the neighbor,
thus making it informed.  Feige et al \cite{feige-rumor} show that the
push process completes in every undirected graph in $O(n \log n)$
steps, with high probability.  Since then, the push protocol and its
variants have been extensively analyzed both for special graphs, as
well as for general graphs in terms of their expansion properties (see
e.g., \cite{panconesi1, panconesi2, panconesi3, gia1, gia2, pana1, pana2}).  Again, though BRWs and rumor spreading share the
property that multiple nodes are active in a given step, the two
mechanisms differ significantly from each other.  While the set of
active nodes in rumor spreading is monotonically nondecreasing, this
is not so in branching random walks, an aspect that makes the analysis
challenging especially with regard to full coverage.  Furthermore, the
message complexity of the push protocol can be substantially different
than that of BRWs.  For instance, for the star network, the push
protocol covers all nodes in $\Theta(n \log n)$ steps with a message
complexity of $\Theta(n^2 \log n)$, while the $2$-branching random
walk has both cover time and message complexity $\Theta(n \log n)$.

%Push process. Feige et al. Panconesi. Giakopoulos.
%Berenbrink. Sauerwald. Censor-Hillel.



%Distributed random walks. Gopal et al.
